package com.leetcode.algorithm.y22.m06;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 139. 单词拆分
 * 
 * https://leetcode.cn/problems/word-break/
 * 
 * @author jie.deng
 *
 */
class Question0139Solution02 {

	public boolean wordBreak(String s, List<String> wordDict) {
		int maxWordLen = 0;
		for (String word : wordDict) {
			if (word.length() > maxWordLen) {
				maxWordLen = word.length();
			}
		}
		Set<String> wordSet = new HashSet<>(wordDict);

		int len = s.length();
		// dp[i]表示s.substring(0, i)是否可以利用字典中出现的单词拼接出 i=endIndex exclusive
		boolean[] dp = new boolean[len + 1];
		dp[0] = true;

		for (int i = 1; i <= len; i++) {
			for (int j = 1; j <= maxWordLen && i - j >= 0; j++) {
				if (dp[i - j] && wordSet.contains(s.substring(i - j, i))) {
					dp[i] = true;
					break;
				}
			}
		}

		return dp[len];
	}

}